
//表示我们要添加到链表中的项
class Node {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}
//LinkedList类表示一个链表，它包含一个头节点、一个尾节点和一个长度属性。
class LinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
        this.length = 0;
    }

    /* append方法用于向链表的末尾添加一个新节点。它首先创建一个新的Node对象，并将其数据设置为data参数。然后，
    它检查链表是否为空。如果链表为空，则将新节点作为头节点和尾节点。
    否则，它将新节点的next属性设置为当前尾节点，并将尾节点设置为新节点。
    最后，它将长度属性加1。 */
    append(data) {
        const newNode = new Node(data);

        if (!this.head) {
            this.head = newNode;
            this.tail = newNode;
        } else {
            this.tail.next = newNode;
            
            this.tail = newNode;
        }

        this.length++;
    }
/* prepend方法用于向链表的开头添加一个新节点。
它与append方法非常相似，但是它将新节点的next属性设置为当前头节点，并将头节点设置为新节点。 */
    prepend(data) {
        const newNode = new Node(data);

        if (!this.head) {
            this.head = newNode;
            this.tail = newNode;
        } else {
            newNode.next = this.head;
            this.head = newNode;
        }

        this.length++;
    }
/* insert方法用于在链表中插入一个新节点。
它首先检查插入的索引是否在0和链表长度之间。
如果索引小于0或大于链表长度，则抛出一个错误。
如果索引等于0，则调用prepend方法将新节点添加到开头。
如果索引等于链表长度，则调用append方法将新节点添加到末尾。
否则，它将创建一个新的Node对象，并将其数据设置为data参数。
然后，它将当前节点和前一个节点存储在变量中，
并使用一个循环找到要插入的位置。
最后，它将前一个节点的next属性设置为新节点，新节点的next属性设置为当前节点，并将长度属性加1。 */
    insert(index, data) {
        if (index < 0 || index > this.length) {
            throw new Error('Index out of bounds');
        }

        if (index === 0) {
            this.prepend(data);
            return;
        }

        if (index === this.length) {
            this.append(data);
            return;
        }

        const newNode = new Node(data);
        let currentNode = this.head;
        let previousNode = null;
        let currentIndex = 0;

        while (currentIndex < index) {
            previousNode = currentNode;
            currentNode = currentNode.next;
            currentIndex++;
        }

        previousNode.next = newNode;
        newNode.next = currentNode;
        this.length++;
    }
/* remove方法用于从链表中删除一个节点。
它首先检查要删除的索引是否在0和链表长度之间。
如果索引小于0或大于链表长度，则抛出一个错误。
然后，它将当前节点和前一个节点存储在变量中，并使用一个循环找到要删除的节点。
最后，它将前一个节点的next属性设置为当前节点的next属性，并将长度属性减1。 */
    remove(index) {
        if (index < 0 || index >= this.length) {
            throw new Error('Index out of bounds');
        }

        let currentNode = this.head;
        let previousNode  = null;
        let currentIndex = 0;
 
        if (index === 0) {
            this.head = currentNode.next;
        } else {
            while (currentIndex < index) {
                previousNode = currentNode;
                currentNode = currentNode.next;
                currentIndex++;
            }

            previousNode.next = currentNode.next;
        }

        this.length--;
    }
/* toArray()方法用于将链表转换为数组。它创建一个空数组result，并将链表中的每个节点的数据添加到数组中。
它使用一个while循环来遍历链表中的每个节点，并将节点的数据添加到result数组中。
当节点为null时，循环结束。最后，它将result数组返回。 */
    toArray() {
        const result = [];
        let currentNode = this.head;

        while (currentNode) {
            result.push(currentNode.data);
            currentNode = currentNode.next;
        }

        return result;
    }
}
